package com.origin.niuke.stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 直方图内最大矩形
 * 算法：单调栈
 * 使用索引来算出宽度
 * [3, 6, 7, 4, 2]
 * 当遍历到最后一个元素并且中间三个元素都被弹出去的时候, 由于 3 比 2 大, 所以 3 也要被弹出
 * 它的宽度可以使用下标索引来确定, 而不是像刚开始做的, 通过弹出元素来确定
 *
 * @author yezh
 * @date 2022/12/26 21:11
 */
public class NC171 {

    public static void main(String[] args) {
//        System.out.println(new NC171().largestRectangleArea(new int[]{3, 4, 7, 8, 1, 2}));
        System.out.println(new NC171().largestRectangleArea(new int[]{1, 7, 3, 2, 4, 5, 8, 2, 7}));
//        System.out.println(new NC171().largestRectangleArea(new int[]{0, 1, 0, 2, 0, 3, 0}));
    }

    public int largestRectangleArea(int[] heights) {
        // write code here
        // 大于等于当前柱子的数量, 而且是要连续
        int ans = 0, n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int curHeight = heights[stack.pop()];
                // 为空表示从 0 开始都 ≥ curHeight
                int l = stack.isEmpty() ? 0 : stack.peek() + 1;
                // [i - l, i - 1] 的数都比 heights[stack.pop()] 大
                ans = Math.max(ans, (i - l) * curHeight);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int curHeight = heights[stack.pop()];
            int l = stack.isEmpty() ? 0 : stack.peek() + 1;
            ans = Math.max(ans, (n - l) * curHeight);
        }
        return ans;
    }

}
